import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-09-30
 * Time: 11:31
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
 }

public class LevelOrder {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists=new ArrayList<>();
        if(root==null){
            return lists;
        }

        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            List<Integer> list=new ArrayList<>();
            //关键点:用队列的size来判断每层的节点数
            int size=queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode=queue.poll();
                if(treeNode!=null){
                    queue.offer(treeNode.left);
                    queue.offer(treeNode.right);
                    list.add(treeNode.val);
                }
            }
            //最后队列不为空但全为null时
            // list.size为0,就不用添加了
            if(list.size()>0){
                lists.add(list);
            }
        }
        return lists;
    }
}
